package Leetcode;


/**
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 */
public class test876 {

    /**
     * 遍历寻找中间节点值
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        //遍历数组，拿到链表的长度
       int count=0;
       ListNode x=head;
       while(x!=null){
           x=x.next;
           count++;
       }
      ListNode mid=head;
       //此时从头节点开始走count/2步，刚好到中间节点位置
       int midNum=count/2;
        for (int i = 0; i <midNum ; i++) {
            mid=mid.next;
        }
        return mid;
    }

    /**
     *使用快慢指针法
     * 快指针走两步，慢指针走一步，到快指针走到null或者快指针的下一个元素为空时，慢指针恰好在中间节点上
     * @param head
     * @return
     */
    public ListNode middleNode1(ListNode head){
        ListNode fast=head;
        ListNode low=head;
        while (fast!=null&&fast.next!=null){
            //快指针走两步
            fast=fast.next.next;
            //慢指针走一步
            low=low.next;
        }
        return low;
    }


}
